package 力扣日常刷题.木23一月.第04天304;

import 力扣日常刷题.ListNode;

/**
 * @author 帅小伙
 * @date 2022/3/4
 * @description
 * 找到中点  归并排序
 */
public class Demo40链表排序 {

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;

        // 分成两个链表进行排序
        ListNode fast = head,slow = head,prev = head;
        while(fast != null && fast.next != null) {
            prev = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        prev.next = null;
        // 两部分链表分别排序
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);

        // 链表进行合并
        return merge(l1,l2);
    }

    public ListNode merge(ListNode l1,ListNode l2) {
        ListNode p = new ListNode(),l = p;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                p.next = l1;
                l1 =l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2 : l1;
        return l.next;
    }

}
